package com.zhanghp.class03;

import com.zhanghp.refer.ListNode;

import java.util.concurrent.atomic.AtomicBoolean;

import static com.zhanghp.refer.ListNode.*;

/**
 * <h1>
 * K个节点的组内逆序调整问题：
 * </h1>
 * <p>
 * 给定一个单链表的头节点head，和一个正数k
 * 实现k个节点的小组内部逆序，如果最后一组不够k个就不调整
 * </p>
 * <ul>
 *     例子:
 *     <li>
 *         调整前：1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8，k = 3
 *     </li>
 *     <li>
 *          调整后：3 -> 2 -> 1 -> 6 -> 5 -> 4 -> 7 -> 8
 *     </li>
 * </ul>
 *
 * <a href = "https://leetcode.cn/problems/reverse-nodes-in-k-group/">leetcode 校验</a>
 * <p>自研</p>
 *
 * @author zhanghp
 * @since 2023/10/16 17:34
 */
public class Code04_ReverseNodesInKGroup {

    public static void main(String[] args) {
        // 生成节点
        ListNode node = generateRandomLinkedList(10, 10);
        ListNode.printLinkedList(node);
        // 实现
        ListNode handle = reverseKGroup(node, 3);
        printLinkedList(handle);
    }


    /**
     * <p>将指定node，按k大小，实现组内逆序</p>
     *
     * @param head 头
     * @param k    大小
     * @return 结果
     */
    public static ListNode reverseKGroup(ListNode head, int k) {
        AtomicBoolean hasCompleteNode = new AtomicBoolean(false);
        // 当前要操作的组头节点（未被反转的）
        ListNode cur = head;
        // 下一组头节点（未被反转过的）
        ListNode nextGroupHeadNode = returnHead(head, k, hasCompleteNode);
        // 当前组的头节点（反转过的）
        ListNode curReverseHeadNode = null;
        // 上一组尾节点（反转过的）
        ListNode preGroupReverseLastNode = null;
        ListNode result;
        // 看node节点是否是小于k的，选择对应不同的头
        // 如：k = 3
        // 1 -> 2 头：1
        // k= 3
        // 1 -> 2 -> 3 头：3
        if (hasCompleteNode.get()) {
            result = getPrintHeadNode(head, k);
        } else {
            result = head;

        }
        while (hasCompleteNode.get()) {
            // 需要前一组的尾结点链接转换后的节点
            curReverseHeadNode = reverseNode(cur, k);
            // 上一组节点不为空，设置它的下一个连接节点
            if (preGroupReverseLastNode != null) {
                preGroupReverseLastNode.next = curReverseHeadNode;
            }
            // 将当前赋值为上一节点，方便赋值下一个连接点
            preGroupReverseLastNode = cur;
            // 当前节点赋值为下一个组节点：方便下一个循环使用
            cur = nextGroupHeadNode;
            // 返回下一组头节点
            nextGroupHeadNode = returnHead(nextGroupHeadNode, k, hasCompleteNode);
            // 下一组若不具备k大小的容量，则会结束循环，所以需要设置当前逆序后的节点所指的下一组节点
            if (!hasCompleteNode.get()) {
                preGroupReverseLastNode.next = cur;
            }

        }
        return result;
    }

    /**
     * <p>获取打印头结点</p>
     * <p>
     * 获取组内足最后一个节点
     * </p>
     *
     * @param node 节点
     * @param size 指定容量
     * @return 第一个组内的尾节点
     */
    private static ListNode getPrintHeadNode(ListNode node, int size) {
        if (node == null) {
            return null;
        }
        ListNode head = node;
        int count = 1;
        while (--size > 0 && node != null) {
            node = node.next;
            count++;
        }
        if (count < size) {
            return head;
        }
        return node;
    }

    /**
     * 指定容量的组逆序
     *
     * @param head 组
     * @param size 逆序的容量
     * @return 逆序后的尾节点
     */
    private static ListNode reverseNode(ListNode head, int size) {
        ListNode pre = null;
        ListNode next = null;
        int count = 0;
        while (head != null && count < size) {
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
            count++;
        }
        return pre;
    }

    /**
     * 返回下一组的头节点
     *
     * @param node 节点
     * @param size 大小
     * @param flag 第一组是否是具备逆序功能
     * @return 头节点
     */
    private static ListNode returnHead(ListNode node, int size, AtomicBoolean flag) {
        if (node == null) {
            flag.set(false);
            return null;
        }
        int count = 0;
        do {
            node = node.next;
            count++;
        } while (node != null && count < size);
        flag.set(count == size);
        return node;
    }


}
